package com.company.algo.niuke;


import com.company.algo.pojo.TreeNode;

import java.util.*;

/**求二叉树的层序遍历
 【自己没做出来】
 */
public class HierarchicalTraversal {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (root == null) return res;
        helper(root,0);
        return res;
    }

    private void helper(TreeNode node, int level){
        if (level == res.size()){
            res.add(new ArrayList<>());
        }
        ArrayList<Integer> list = res.get(level);
        list.add(node.val);
        if (node.left!=null) helper(node.left,level+1);
        if (node.right!=null) helper(node.right,level+1);
    }

    public ArrayList<ArrayList<Integer>> levelOrder2(TreeNode root) {
        //这道提题目在之前做过，但是经历了今天的练习也算是有一个意识上的突破，以前我希望在加入队列之前就把
        //相关的数据加入结果集合中，但是殊不知在加入队列之后再加入结果集也是可以的。
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(root != null){
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                //遍历的时候加入结果集合也是可以的，而且更简便
                ArrayList<Integer> newLevel = new ArrayList<>();
                for(int i=0; i<size; i++){
                    TreeNode temp = queue.poll();
                    newLevel.add(temp.val);
                    if(temp.left != null) queue.offer(temp.left);
                    if(temp.right != null) queue.offer(temp.right);
                }
                result.add(newLevel);
            }
        }
        return result;
    }
}
